# 合并k个升序链表： https://leetcode-cn.com/problems/merge-k-sorted-lists/submissions/


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# 采用递归求解 两个链表合并， 能过，但是花了6392ms~~~ 效率不高
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        """
            递归， 可以直接写一个方法合并两个，再一次顺序合并
        """
        def merge(l1, l2):
            # 递归终止条件， 一个为None，直接返回剩余
            if not l1:
                return l2
            elif not l2:
                return l1

            # 1. 寻找当前节点
            # 2. 回溯时，确定其next指向
            # 3. 返回当前节点
            if l1.val < l2.val:
                l1.next = merge(l1.next, l2)
                return l1
            else:
                l2.next = merge(l1, l2.next)
                return l2

        # 空列表直接返回 None
        if not lists: return None

        n = len(lists)
        rst = lists[0]
        # 顺序依次合并
        for i in range(1, n):
            rst = merge(rst, lists[i])

        return rst


# 迭代，也是6992 ms
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        """
            迭代
        """
        def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
            # 设立一个首元结点
            h = ListNode()
            cur = h
            while l1 or l2:
                # 值的范围为 [-100, 100], 那么当没有节点时，就取 101
                a = l1.val if l1 else 101
                b = l2.val if l2 else 101

                if a < b:
                    p1 = l1
                    l1 = l1.next
                    cur.next = p1
                else:
                    p2 = l2
                    l2 = l2.next
                    cur.next = p2
                cur = cur.next
        
            return h.next

        # 空列表直接返回 None
        if not lists: return None

        n = len(lists)
        rst = lists[0]
        # 顺序依次合并
        for i in range(1, n):
            rst = mergeTwoLists(rst, lists[i])

        return rst


# 分治递归求解： 92ms！！！ 不太理解为何性能会如此优异，可以看看官方题解
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        """
            迭代
        """
        def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
            # 设立一个首元结点
            h = ListNode()
            cur = h
            while l1 or l2:
                # 值的范围为 [-100, 100], 那么当没有节点时，就取 101
                a = l1.val if l1 else 101
                b = l2.val if l2 else 101

                if a < b:
                    p1 = l1
                    l1 = l1.next
                    cur.next = p1
                else:
                    p2 = l2
                    l2 = l2.next
                    cur.next = p2
                cur = cur.next
        
            return h.next

        # 空列表直接返回 None
        if not lists: return None
        
        def fenzhi(lists, left, right):
            """
                类似于归并排序了，  分治思路求解递归
            """
            # 4. 递归终止条件，最深时， left == right 只有一个节点，返回该节点， 它的上一级只有两个节点，方可向下运行合并操作
            # 可以画图理解一下，递归回溯过程！！ 弄明白
            if left >= right:
                print(left, right)
                return lists[left]

            # 求中间值，    
            middle = (left + right) // 2
            # 1. 返回左边链表
            p1 = fenzhi(lists, left, middle)
            # 2. 返回右边链表
            p2 = fenzhi(lists, middle + 1, right)

            # 3. 求左右两边结果，返回上一级
            return mergeTwoLists(p1, p2)


        # 分治最终结果
        rst = fenzhi(lists, 0, len(lists) - 1)

        return rst



